package list

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	old := head.Next
	for old != nil {
		var pre *ListNode
		cur, old, oNext := head, head.Next, old.Next
		for ; cur != nil && cur.Val <= old.Val; cur = cur.Next {
			pre = cur
		}
		if pre == nil {
			head = old
		} else {
			pre.Next = old
		}
		old.Next = cur
		old = oNext

	}
	return head
}
